package com.burns.leetcode.d508t;

import java.util.*;

/**
 * 给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
 *
 * 一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/most-frequent-subtree-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Main1 {
    public static void main(String[] args) {
        TreeNode1 root = initData();
        int[] frequentTreeSum = findFrequentTreeSum(root);
        System.out.println(frequentTreeSum);
    }

    private static TreeNode1 initData() {
        TreeNode1 left=new TreeNode1(2);
        TreeNode1 right=new TreeNode1(-3);
        TreeNode1 root=new TreeNode1(5,left,right);

        return root;
    }

    public static int[] findFrequentTreeSum(TreeNode1 root) {
        List<Integer> resultList = new ArrayList<>() ;
        Map<Integer,Integer> valAndNumMap = new HashMap<>();
        handle(valAndNumMap,root);
        int maxVal = getMaxValue(valAndNumMap);
        Set<Map.Entry<Integer, Integer>> entries = valAndNumMap.entrySet();
        for(Map.Entry<Integer,Integer> entry:entries){
            if(maxVal==entry.getValue()){
                resultList.add(entry.getKey());
            }
        }
        int[] result = new int[resultList.size()];
        for(int i=0;i<resultList.size();i++){
            result[i]=resultList.get(i);
        }
        return result;


    }

    private static int getMaxValue(Map<Integer, Integer> valAndNumMap) {
        int maxVal = 0;
        Iterator<Integer> valIterator = valAndNumMap.values().iterator();
        while (valIterator.hasNext()){
            Integer next = valIterator.next();
            if(maxVal<next){
                maxVal=next;
            }
        }
        return maxVal;

    }

    private static void handle(Map<Integer, Integer> valAndNumMap, TreeNode1 root) {
        if(root!=null){
            valAndNumMap.put(root.val,1);
            if ((root.left != null || root.right != null)) {
                if(root.left!=null){
                    Integer leftNum = valAndNumMap.get(root.left.val);
                    if(leftNum==null){
                        valAndNumMap.put(root.left.val,1);
                    }else {
                        valAndNumMap.put(root.left.val,leftNum+1);
                    }
                    handle(valAndNumMap,root.left);
                }

                if(root.right!=null){
                    Integer rightNum = valAndNumMap.get(root.right.val);
                    if(rightNum==null){
                        valAndNumMap.put(root.right.val,1);
                    }else {
                        valAndNumMap.put(root.right.val,rightNum+1);
                    }
                    handle(valAndNumMap,root.right);
                }
            }
        }
    }
}

class TreeNode1 {
    int val;
    TreeNode1 left;
    TreeNode1 right;

    TreeNode1() {
    }

    TreeNode1(int val) {
        this.val = val;
    }

    TreeNode1(int val, TreeNode1 left, TreeNode1 right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
